package code.oldCode.classic150;

import java.util.*;

/**
 * @author cuihaoran
 * @date 2024/12/17
 */
public class Classic150_hash {
    /* 383. 赎金信 */
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        int len = magazine.length();
        int noteLen = ransomNote.length();
        for (int i = 0; i < len; i++) {
            Character c = magazine.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < noteLen; i++) {
            Character c = ransomNote.charAt(i);
            if (!map.containsKey(c) || map.get(c) == 0)
                return false;
            else
                map.put(c, map.get(c) - 1);
        }
        return true;
    }

    /* 205. 同构字符串 */
    public boolean isIsomorphic(String s, String t) {
        int len = s.length();
        Map<Character, Character> mapS_T = new HashMap<>();
        Map<Character, Character> mapT_S = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Character cS = s.charAt(i);
            Character cT = t.charAt(i);
            // s->t
            if (!mapS_T.containsKey(cS)) {
                mapS_T.put(cS, cT);
            } else if (mapS_T.get(cS) != cT) {
                return false;
            }
            // t->s
            if (!mapT_S.containsKey(cT)) {
                mapT_S.put(cT, cS);
            } else if (mapT_S.get(cT) != cS) {
                return false;
            }
        }
        return true;
    }

    /* 290. 单词规律 */
    public boolean wordPattern(String pattern, String s) {
        int len = pattern.length();
        String[] s1 = s.split(" ");
        if (len != s1.length)
            return false;
        Map<Character, String> cs = new HashMap<>();
        Map<String, Character> sc = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Character cc = pattern.charAt(i);
            String ss = s1[i];
            if (!cs.containsKey(cc)) {
                cs.put(cc, ss);
            } else if (!cs.get(cc).equals(ss)) {
                return false;
            }
            if (!sc.containsKey(ss)) {
                sc.put(ss, cc);
            } else if (sc.get(ss) != cc) {
                return false;
            }
        }

        return true;
    }

    /* 242. 有效的字母异位词 */
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length())
            return false;
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < len; i++) {
            Character c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for (int i = 0; i < len; i++) {
            Character c = t.charAt(i);
            if (!map.containsKey(c) || map.get(c) == 0)
                return false;
            map.put(c, map.get(c) - 1);
        }
        return true;
    }

    /* 49. 字母异位词分组
     * 输出：[["ac","c"]] 预期结果：[["c"],["ac"]]
     * 明明是一样的却不给过，离谱
     * */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> lists = new ArrayList<>();
        List<HashMap<Character, Integer>> mapList = new ArrayList<>();
        for (String s : strs) {
            // 在当前mapList中查找
            int mapListLen = mapList.size();
            int sLen = s.length();
            int findPos = -1;
            for (int i = 0; i < mapListLen; i++) {
                boolean find = true;
                HashMap<Character, Integer> tempMap = new HashMap<>();
                for (int j = 0; j < sLen; j++) {
                    Character c = s.charAt(j);
                    if (mapList.get(i).containsKey(c)) {
                        tempMap.put(c, tempMap.getOrDefault(c, 0) + 1);
                        if (tempMap.get(c) > mapList.get(i).get(c)) {
                            find = false;
                            break;
                        }
                    } else {
                        find = false;
                    }
                }
                if (find) {
                    findPos = i;
                    break;
                }
            }
            // 找到了
            if (findPos >= 0) {
                lists.get(findPos).add(s);
            }
            // 没找到
            else {
                HashMap<Character, Integer> addMap = new HashMap<>();
                List<String> addList = new ArrayList<>();
                for (int i = 0; i < sLen; i++) {
                    Character c = s.charAt(i);
                    addMap.put(c, addMap.getOrDefault(c, 0) + 1);
                }
                mapList.add(addMap);
                addList.add(s);
                lists.add(addList);
            }
        }
        return lists;
    }

    /* 49. 字母异位词分组 更简洁的方法 */
    public List<List<String>> groupAnagrams_newWay(String[] strs) {
        List<List<String>> lists = new ArrayList<>();
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] charArray = s.toCharArray();
            Arrays.sort(charArray);
            String sortedS = Arrays.toString(charArray);
            if (!map.containsKey(sortedS)) {
                map.put(sortedS, new ArrayList<>());
            }
            map.get(sortedS).add(s);
        }
        map.forEach((key, value) -> lists.add(value));
        return lists;
    }

    /* 1. 两数之和 */
    public int[] twoSum_(int[] nums, int target) {
        // 这个题有重复，忽略即可
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }

    /* 202. 快乐数 */
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (true) {
            // 判断这个数
            if (set.contains(n))
                return false;
            if (n == 1)
                return true;
            set.add(n);
            // 确定下一个数
            int sum = 0;
            while (n > 0) {
                int temp = n % 10;
                sum += temp * temp;
                n /= 10;
            }
            n = sum;
        }
    }

    /* 219. 存在重复元素 II */
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            if (!map.containsKey(nums[i]))
                map.put(nums[i], i);
            else {
                if (i - map.get(nums[i]) <= k)
                    return true;
                map.put(nums[i], i);
            }
        }
        return false;
    }

    /* 128. 最长连续序列 */
    public int longestConsecutive(int[] nums) {
        // [0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999] 超时
        if (nums.length == 0)
            return 0;
        int min = Arrays.stream(nums).min().getAsInt();
        int max = Arrays.stream(nums).max().getAsInt();
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }
        int pos = min;
        int now = 0;
        int ans = 0;
        // 超时的原因在这，遍历每个数太慢了，得想办法只遍历有的数
        while (pos <= max) {
            if (set.contains(pos) && (now == 0 || set.contains(pos - 1))) {
                now++;
            } else {
                now = 1;
            }
            pos++;
            ans = Math.max(ans, now);
        }
        return ans;
    }

    /* 128. 最长连续序列-优化 */
    public int longestConsecutive_fix(int[] nums) {
        // [0,1,2,4,8,5,6,7,9,3,55,88,77,99,999999999]
        HashMap<Integer, Integer> map = new HashMap<>(); // key表示数，value表示当前链条的长度，0代表还没被遍历到
        for (int num : nums) {
            map.put(num, 0);
        }
        int max = 0;
        for (Integer key : map.keySet()) {
            // 如果当前key的value已经不是0了，说明这个数遍历过了，跳过即可
            if (map.get(key) != 0)
                continue;
            // 将这个key的value设置为1
            map.put(key, 1);
            // 往后寻找，如果下一个数存在，循环
            int next = key + 1; // 下一个要找的key
            int findCount = 0; // 找到的未被遍历的数量
            while (map.containsKey(next)) {
                int nextValue = map.get(next);
                // value不是0，说明下一个数被遍历过，当前value = 下一个的value + 1
                if (nextValue != 0) {
                    map.put(key, nextValue + 1);
                    break;
                }
                // value是0，说明下一个数没被遍历过
                else {
                    map.put(next, 1);
                    findCount++;
                    next++;
                }
            }
            map.put(key, map.get(key) + findCount);
            max = Math.max(max, map.get(key));
        }
        return max;
        // 官解的方法更巧妙，遍历map，如果包括key-1，直接跳过...，所以遍历到的都是链条的开头，好理解一些。
    }
}
